import java.util.List;

public class Test {


    public static void main(String[] args) {
    }
    //166.珠宝的最高价值
    public int jewelleryValue(int[][] frame) {
        int m = frame.length;
        int n = frame[0].length;
        int[][] dp = new int[m][n];
        dp[0][0] = frame[0][0];
        for(int i=1;i<n;i++) dp[0][i] = dp[0][i-1]+frame[0][i];
        for(int i=1;i<m;i++) dp[i][0] = dp[i-1][0]+frame[i][0];
        for(int i=1;i<m;i++) {
            for(int j=1;j<n;j++) {
                dp[i][j] = Math.max(dp[i-1][j],dp[i][j-1]) + frame[i][j];
            }
        }
        return dp[m-1][n-1];
    }
    //汉诺塔

    public void hanota(List<Integer> A, List<Integer> B, List<Integer> C) {
        dfs(A,B,C,A.size());
    }
    public void dfs(List<Integer> a,List<Integer> b,List<Integer> c,int n) {
        if(n == 1) {
            c.add(a.remove(a.size()-1));
            return;
        }
        dfs(a,c,b,n-1);
        c.add(a.remove(a.size()-1));
        dfs(b,a,c,n-1);
    }

}
